CODE 36. Interleaving String

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 36 Interleaving String/

访问原文「CODE 36. Interleaving String」

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

public boolean isInterleave(String s1, String s2, String s3) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == s1 && null == s2 && null == s3) {
		return true;
	} else if (null == s1 && null == s2 && null != s3) {
		return false;
	} else if (null == s1) {
		if (s2.equals(s3)) {
			return true;
		} else {
			return false;
		}
	} else if (null == s2) {
		if (s1.equals(s3)) {
			return true;
		} else {
			return false;
		}
	} else if (null != s1 && null != s2 && null != s3) {
		if (s3.length() != s1.length() + s2.length()) {
			return false;
		}
	}

	boolean[][] is = new boolean[s1.length() + 1][s2.length() + 1];
	is[0][0] = true;
	for (int i = 1; i < s1.length() + 1; i++) {
		if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
			is[i][0] = true && is[i - 1][0];
		}
	}
	for (int i = 1; i < s2.length() + 1; i++) {
		if (s2.charAt(i - 1) == s3.charAt(i - 1)) {
			is[0][i] = true & is[0][i - 1];
		}
	}
	for (int i = 1; i < s1.length() + 1; i++) {
		for (int j = 1; j < s2.length() + 1; j++) {
			boolean b1 = false;
			boolean b2 = false;
			if (s3.charAt(i + j - 1) == s1.charAt(i - 1)) {
				b1 = is[i - 1][j];
			}
			if (s3.charAt(i + j - 1) == s2.charAt(j - 1)) {
				b2 = is[i][j - 1];
			}
			is[i][j] = b1 || b2;
		}
	}
	return is[s1.length()][s2.length()];
	// return dfs(s1, s2, s3, 0, 0, 0);
}